{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Lines to Represent a Line Chart"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math #number-theory #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学 #数论 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumLines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #表示一个折线图的最少线段数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组&nbsp;<code>stockPrices</code> ，其中&nbsp;<code>stockPrices[i] = [day<sub>i</sub>, price<sub>i</sub>]</code>&nbsp;表示股票在&nbsp;<code>day<sub>i</sub></code>&nbsp;的价格为&nbsp;<code>price<sub>i</sub></code>&nbsp;。<strong>折线图</strong>&nbsp;是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/30/1920px-pushkin_population_historysvg.png\" style=\"width: 500px; height: 313px;\">\n",
    "<p>请你返回要表示一个折线图所需要的 <strong>最少线段数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/30/ex0.png\" style=\"width: 400px; height: 400px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "上图为输入对应的图，横坐标表示日期，纵坐标表示价格。\n",
    "以下 3 个线段可以表示折线图：\n",
    "- 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。\n",
    "- 线段 2 （蓝色）从 (4,4) 到 (5,4) 。\n",
    "- 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。\n",
    "可以证明，无法用少于 3 条线段表示这个折线图。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/30/ex1.png\" style=\"width: 325px; height: 325px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>stockPrices = [[3,4],[1,2],[7,8],[2,3]]\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>\n",
    "如上图所示，折线图可以用一条线段表示。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= stockPrices.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>stockPrices[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= day<sub>i</sub>, price<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>所有&nbsp;<code>day<sub>i</sub></code>&nbsp;<strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-lines-to-represent-a-line-chart](https://leetcode.cn/problems/minimum-lines-to-represent-a-line-chart/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-lines-to-represent-a-line-chart](https://leetcode.cn/problems/minimum-lines-to-represent-a-line-chart/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]', '[[3,4],[1,2],[7,8],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum((dx0*dy1!=dx1*dy0) for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, a: List[List[int]]) -> int:\n",
    "        a.sort()\n",
    "        py, px = 1 ,0\n",
    "        ans = 0\n",
    "        for i in range(1, len(a)):\n",
    "            dy =a[i][1]-a[i-1][1]\n",
    "            dx =a[i][0]-a[i-1][0]\n",
    "\n",
    "            if dy * px != dx * py:\n",
    "                ans +=1\n",
    "                py = dy\n",
    "                px = dx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2,n):\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d0,p0 = stockPrices[0]\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-d0,p1-p0\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            if d21*p10!=d10*p21:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) <= 1:\n",
    "            return 0\n",
    "        stockPrices.sort(key=lambda x: x[0])\n",
    "        ans = 1\n",
    "        for i in range(2, len(stockPrices)):\n",
    "            x1, y1 = stockPrices[i - 2]\n",
    "            x2, y2 = stockPrices[i - 1]\n",
    "            x3, y3 = stockPrices[i]\n",
    "            if (x2 - x1) * (y3 - y2) != (x3 - x2) * (y2 - y1):\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        def slope(p1: List[int], p2: List[int]) -> Tuple[int, int]:\n",
    "            x1, y1 = p1; x2, y2 = p2\n",
    "            gcd_ = gcd(y2 - y1, x2 - x1)\n",
    "\n",
    "            return (y2 - y1) // gcd_,  (x2 - x1) // gcd_\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        stockPrices.sort()\n",
    "        p1 = stockPrices[0]\n",
    "        p2 = stockPrices[1]\n",
    "        slope1 = slope(p1, p2)\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            p3 = stockPrices[i]\n",
    "            slope2 = slope(p2, p3)\n",
    "            if slope1[0] != slope2[0] or slope1[1] != slope2[1]:\n",
    "                res += 1\n",
    "            slope1, p1, p2 = slope2, p2, p3\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        def slope(p1: List[int], p2: List[int]) -> Tuple[int, int]:\n",
    "            x1, y1 = p1; x2, y2 = p2\n",
    "            gcd_ = gcd(y2 - y1, x2 - x1)\n",
    "            return (y2 - y1) // gcd_,  (x2 - x1) // gcd_\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        stockPrices.sort()\n",
    "        p1 = stockPrices[0]\n",
    "        p2 = stockPrices[1]\n",
    "        slope1 = slope(p1, p2)\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            p3 = stockPrices[i]\n",
    "            slope2 = slope(p2, p3)\n",
    "            if slope1[0] != slope2[0] or slope1[1] != slope2[1]:\n",
    "                res += 1\n",
    "            slope1, p1, p2 = slope2, p2, p3\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        l = len(stockPrices)\n",
    "        mls = int(l>1)\n",
    "        for i in range(l-2):\n",
    "            if (stockPrices[i+2][0]-stockPrices[i+1][0])*(stockPrices[i+1][1]-stockPrices[i][1])!=(stockPrices[i+1][0]-stockPrices[i][0])*(stockPrices[i+2][1]-stockPrices[i+1][1]):\n",
    "                mls += 1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def judge(x1,y1,x2,y2,x3,y3):\n",
    "    return (x2-x1)*(y3-y1)==(x3-x1)*(y2-y1)\n",
    "class Solution:\n",
    "    def minimumLines(self, arr: List[List[int]]) -> int:\n",
    "        n=len(arr)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        if n==2:\n",
    "            return 1\n",
    "        arr.sort(key=lambda x:x[0])\n",
    "        res=1\n",
    "        for i in range(2,n):\n",
    "            x1,y1=arr[i-2]\n",
    "            x2,y2=arr[i-1]\n",
    "            x3,y3=arr[i]\n",
    "            if not judge(x1,y1,x2,y2,x3,y3):\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            # 遍历相邻点对，并判断线段是否可以合并\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/minimum-lines-to-represent-a-line-chart/solutions/1538682/biao-shi-yi-ge-zhe-xian-tu-de-zui-shao-x-gwnk/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum((dx0*dy1!=dx1*dy0) for (dx0,dy0),(dx1,dy1) in pairwise(((x2-x1),(y2-y1)) for (x1,y1),(x2,y2) in pairwise(stockPrices)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        l = len(stockPrices)\n",
    "        return (l>1)+sum((stockPrices[i+1][0]-stockPrices[i][0])*(stockPrices[i][1]-stockPrices[i-1][1])!=(stockPrices[i][0]-stockPrices[i-1][0])*(stockPrices[i+1][1]-stockPrices[i][1]) for i in range(1,l-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort(key=lambda x: x[0])\n",
    "        ans, pre_dy, pre_dx = 0, 1, 0\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            dy, dx = y2 - y1, x2 - x1\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                ans += 1\n",
    "                pre_dy, pre_dx = dy, dx\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, a: List[List[int]]) -> int:\n",
    "        a.sort()\n",
    "        prex, prey = 0, 1 \n",
    "        ans = 0\n",
    "        n = len(a)\n",
    "        for i in range(1, n):\n",
    "            dy = a[i][1] - a[i - 1][1]\n",
    "            dx = a[i][0] - a[i - 1][0]\n",
    "\n",
    "            if dy * prex != dx * prey:\n",
    "                ans += 1\n",
    "                prex, prey = dx, dy \n",
    "        return ans \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        n, nums = len(stockPrices), sorted(stockPrices)\n",
    "        res, dv, dd = 0, None, None\n",
    "        for i in range(1,n):\n",
    "            tv, td = (nums[i][1]-nums[i-1][1]), (nums[i][0]-nums[i-1][0])\n",
    "            if not dd or tv * dd != td * dv:\n",
    "                res, dv, dd = res+1, tv, td\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        ans=1\n",
    "        n=len(stockPrices)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        stockPrices.sort(key=lambda x:x[0])\n",
    "        for i in range(1,n-1):\n",
    "          a=stockPrices[i-1]  \n",
    "          x=stockPrices[i]\n",
    "          y=stockPrices[i+1]\n",
    "          if (x[1]-a[1])*(y[0]-x[0])!=(y[1]-x[1])*(x[0]-a[0]):\n",
    "             ans+=1\n",
    "        return ans      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        ans, pre_dy, pre_dx = 0, 1, 0\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            dy, dx = y2 - y1, x2 - x1\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                ans += 1\n",
    "                pre_dy, pre_dx = dy, dx\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        l = len(stockPrices)\n",
    "        return (l>1)+sum((stockPrices[i+2][0]-stockPrices[i+1][0])*(stockPrices[i+1][1]-stockPrices[i][1])!=(stockPrices[i+1][0]-stockPrices[i][0])*(stockPrices[i+2][1]-stockPrices[i+1][1]) for i in range(l-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            # 遍历相邻点对，并判断线段是否可以合并\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        stockPrices.sort()\n",
    "        for i in range(len(stockPrices) - 2):\n",
    "            k1 = (stockPrices[i][1] - stockPrices[i + 1][1]) * (stockPrices[i + 1][0] - stockPrices[i + 2][0])\n",
    "            k2 = (stockPrices[i + 1][1] - stockPrices[i + 2][1]) * (stockPrices[i][0] - stockPrices[i + 1][0])\n",
    "            if k1 != k2:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        mls = int(len(stockPrices)>1)\n",
    "        for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)):\n",
    "            if dx0*dy1!=dx1*dy0:\n",
    "                mls += 1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        res,dx,dy=0,0,1\n",
    "        for (x1,y1),(x2,y2) in pairwise(stockPrices):\n",
    "            if dx*(y2-y1)!=dy*(x2-x1): res +=1\n",
    "            dx,dy=x2-x1,y2-y1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        l = len(stockPrices)\n",
    "        if l==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i1,j1 = stockPrices[0]\n",
    "        i2,j2 = stockPrices[1]\n",
    "        i21,j21 = i2-i1,j2-j1\n",
    "        for i in range(2,l):\n",
    "            i3,j3 = stockPrices[i]\n",
    "            i32,j32 = i3-i2,j3-j2\n",
    "            if i32*j21!=i21*j32:\n",
    "                mls += 1\n",
    "            i2,j2 = i3,j3\n",
    "            i21,j21 = i32,j32\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        ret  = n-1\n",
    "        for i in range(1, n-1):\n",
    "            dx1, dx2 = stockPrices[i][0] - stockPrices[i-1][0], stockPrices[i+1][0] - stockPrices[i][0]\n",
    "            dy1, dy2 = stockPrices[i][1] - stockPrices[i-1][1], stockPrices[i+1][1] - stockPrices[i][1]\n",
    "            if dx1 * dy2 == dy1 * dx2:\n",
    "                ret -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        mls,pre_dy,pre_dx = 0,1,0\n",
    "        for (x1,y1),(x2,y2) in pairwise(stockPrices):\n",
    "            dy,dx = y2-y1,x2-x1\n",
    "            if dy*pre_dx!=pre_dy*dx:\n",
    "                mls += 1\n",
    "                pre_dy,pre_dx = dy,dx\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort(key = lambda x: x[0])\n",
    "        ans = 0\n",
    "        pre = [1, inf]\n",
    "        for i in range(1, len(stockPrices)):\n",
    "            if (stockPrices[i][1] - stockPrices[i-1][1]) * pre[0] != pre[1] * (stockPrices[i][0] - stockPrices[i-1][0]):\n",
    "                ans += 1\n",
    "                pre = [stockPrices[i][0] - stockPrices[i-1][0], stockPrices[i][1] - stockPrices[i-1][1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2,n):\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        L = len(stockPrices)\n",
    "        if L == 1: return 0 \n",
    "        if L == 2: return 1 \n",
    "\n",
    "        stockPrices = sorted(stockPrices)\n",
    "        line = 1 \n",
    "        for idx in range(2, L): \n",
    "            x1, y1 = stockPrices[idx - 2]\n",
    "            x2, y2 = stockPrices[idx - 1]\n",
    "            x3, y3 = stockPrices[idx]\n",
    "\n",
    "            if (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1): \n",
    "                line += 1 \n",
    "\n",
    "        return line \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        res=0\n",
    "        for i,(x,y) in enumerate(stockPrices):\n",
    "            if i==0: continue\n",
    "            if i==1 or (y-stockPrices[i-1][1])*(x-stockPrices[i-2][0])!=(y-stockPrices[i-2][1])*(x-stockPrices[i-1][0]): res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        it = ((v2-v1, d2-d1) for (d1, v1), (d2, v2) in zip(stockPrices, stockPrices[1:]))\n",
    "        v,d = 1, 0\n",
    "        result = 0\n",
    "        for dv, dd in it:\n",
    "            if v*dd != dv*d: result += 1\n",
    "            v, d = dv, dd\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        ret = 1\n",
    "        stockPrices.sort()\n",
    "        for i in range(2, len(stockPrices)):\n",
    "            y1 = stockPrices[i - 1][1] - stockPrices[i - 2][1]\n",
    "            x1 = stockPrices[i - 1][0] - stockPrices[i - 2][0]\n",
    "            \n",
    "            y2 = stockPrices[i][1] - stockPrices[i - 1][1]\n",
    "            x2 = stockPrices[i][0] - stockPrices[i - 1][0]\n",
    "            \n",
    "            if y1 * x2 != y2 * x1:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        mls,pre_dx,pre_dy = 0,0,1\n",
    "        for (x1,y1),(x2,y2) in pairwise(stockPrices):\n",
    "            dy,dx = y2-y1,x2-x1\n",
    "            if dy*pre_dx!=pre_dy*dx:\n",
    "                mls += 1\n",
    "                pre_dy,pre_dx = dy,dx\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        answer = 1 \n",
    "        stockPrices.sort(key=lambda x:x[0])\n",
    "        pre_dy, pre_dx = stockPrices[1][1] - stockPrices[0][1], stockPrices[1][0] - stockPrices[0][0]\n",
    "        pre_y, pre_x = stockPrices[1][1], stockPrices[1][0]\n",
    "        for stockPrice in stockPrices[2:]:\n",
    "            dy, dx = stockPrice[1] - pre_y, stockPrice[0] - pre_x\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                answer += 1 \n",
    "                pre_dy, pre_dx = dy, dx\n",
    "            pre_y, pre_x = stockPrice[1], stockPrice[0]\n",
    "        return answer\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        ans = 0\n",
    "        last = None\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            # x值不可能相同，因此除以x的差\n",
    "            new = Decimal(y2 - y1) / (x2 - x1)\n",
    "            if new != last:\n",
    "                ans += 1\n",
    "                last = new\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        ans = 1\n",
    "        x, y = stockPrices[1][0] - stockPrices[0][0], stockPrices[1][1] - stockPrices[0][1]\n",
    "        for i in range(2, n):\n",
    "            xi, yi = stockPrices[i][0] - stockPrices[i - 1][0], stockPrices[i][1] - stockPrices[i - 1][1]\n",
    "            if xi * y != yi * x:\n",
    "                ans += 1\n",
    "                x, y = xi, yi\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort(key=itemgetter(0))\n",
    "        ans, pre_dy, pre_dx = 0, 1, 0\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            dy, dx = y2 - y1, x2 - x1\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                ans += 1\n",
    "                pre_dy, pre_dx = dy, dx\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, s: List[List[int]]) -> int:\n",
    "        s.sort()\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        if len(s) == 2:\n",
    "            return 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(2, len(s)):\n",
    "            x1, y1 = s[i - 2]\n",
    "            x2, y2 = s[i - 1]\n",
    "            x3, y3 = s[i]\n",
    "            if (x1 - x2) * (y3 - y1) != (y1 - y2) * (x3 - x1):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stock: List[List[int]]) -> int:\n",
    "        stock.sort()\n",
    "        pre = (-1, -1)\n",
    "        ans = 0\n",
    "        for (x, y), (a, b) in pairwise(stock):\n",
    "            if x == a:\n",
    "                cur = (x, -1)\n",
    "            else:\n",
    "                g = math.gcd(b-y, a-x)\n",
    "                bb = (b-y)//g\n",
    "                aa = (a-x)//g\n",
    "                if aa < 0:\n",
    "                    aa *= -1\n",
    "                    bb *= -1\n",
    "                cur = (bb, aa)\n",
    "            ans += pre != cur\n",
    "            pre = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        from fractions import Fraction\n",
    "        stockPrices.sort()\n",
    "        pre_teng=math.inf\n",
    "        ans = 0\n",
    "        n= len (stockPrices)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dy = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            dx = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            if Fraction(dy,dx) != pre_teng:\n",
    "                ans += 1\n",
    "                pre_teng = Fraction(dy,dx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        if len(stockPrices) == 2:\n",
    "            return 1\n",
    "\n",
    "        cnt = 1\n",
    "\n",
    "        day2, price2 = stockPrices[1]\n",
    "        day1, price1 = stockPrices[0]\n",
    "\n",
    "        dx0 = day2 - day1\n",
    "        dy0 = price2 - price1\n",
    "\n",
    "        for i in range(2,len(stockPrices)):\n",
    "            day2, price2 = stockPrices[i]\n",
    "            day1, price1 = stockPrices[i-1]\n",
    "                \n",
    "            dx1 = day2 - day1\n",
    "            dy1 = price2 - price1\n",
    "\n",
    "\n",
    "            if dy0*dx1 != dx0 * dy1:\n",
    "                cnt += 1\n",
    "                dx0 = dx1\n",
    "                dy0 = dy1\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        from fractions import Fraction\n",
    "        stockPrices.sort()\n",
    "        pre_teng=math.inf\n",
    "        ans = 0\n",
    "        n= len (stockPrices)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dy = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            dx = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            if Fraction(dy,dx) != pre_teng:\n",
    "                ans += 1\n",
    "                pre_teng = Fraction(dy,dx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        l = len(stockPrices)\n",
    "        if l==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i0,j0 = stockPrices[0]\n",
    "        i1,j1 = stockPrices[1]\n",
    "        i10,j10 = i1-i0,j1-j0\n",
    "        for i in range(2,l):\n",
    "            i2,j2 = stockPrices[i]\n",
    "            i21,j21 = i2-i1,j2-j1\n",
    "            if i21*j10!=i10*j21:\n",
    "                mls += 1\n",
    "            i1,j1 = i2,j2\n",
    "            i10,j10 = i21,j21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, s: List[List[int]]) -> int:\n",
    "        s.sort()\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        if len(s) == 2:\n",
    "            return 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(2, len(s)):\n",
    "            x1, y1 = s[i - 2]\n",
    "            x2, y2 = s[i - 1]\n",
    "            x3, y3 = s[i]\n",
    "            if (x1 - x2) * (y3 - y1) != (y1 - y2) * (x3 - x1):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        l = len(stockPrices)\n",
    "        if l==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i1,o1 = stockPrices[0]\n",
    "        i2,o2 = stockPrices[1]\n",
    "        i21,o21 = i2-i1,o2-o1\n",
    "        for i in range(2,l):\n",
    "            i3,o3 = stockPrices[i]\n",
    "            i32,o32 = i3-i2,o3-o2\n",
    "            if i32*o21!=i21*o32:\n",
    "                mls += 1\n",
    "            i2,o2 = i3,o3\n",
    "            i21,o21 = i32,o32\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        # 从第三点开始，斜率不同就加1\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        \n",
    "        ans = 1\n",
    "        for i in range(2, n):\n",
    "            x1, y1 = stockPrices[i-2]\n",
    "            x2, y2 = stockPrices[i-1]\n",
    "            x3, y3 = stockPrices[i]\n",
    "            if (y1-y2) * (x3-x2) != (y3-y2) * (x1-x2):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        stack = []\n",
    "        n = len(stockPrices)\n",
    "        for i in range(1, n):\n",
    "            x, y = stockPrices[i-1]\n",
    "            a, b = stockPrices[i]\n",
    "            if x == a:\n",
    "                cur = (x, -1)\n",
    "            else:\n",
    "                g = math.gcd(b-y, a-x)\n",
    "                bb = (b-y)//g\n",
    "                aa = (a-x)//g\n",
    "                if aa < 0:\n",
    "                    aa *= -1\n",
    "                    bb *= -1\n",
    "\n",
    "                cur = (bb, aa)\n",
    "            if stack and stack[-1] == cur:\n",
    "                continue\n",
    "            stack.append(cur)\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\r\n",
    "        # sort stockPrices by x\r\n",
    "        stockPrices.sort(key=lambda x: x[0])\r\n",
    "        res = len(stockPrices) - 1\r\n",
    "        if len(stockPrices) == 1:\r\n",
    "            return res\r\n",
    "\r\n",
    "        start_point = stockPrices[0]\r\n",
    "        for i, _price in enumerate(stockPrices):\r\n",
    "            if i == 0:\r\n",
    "                continue\r\n",
    "            if _price == stockPrices[-1]:\r\n",
    "                return res\r\n",
    "\r\n",
    "            if (stockPrices[i + 1][1] - stockPrices[i][1]) * (start_point[0] - stockPrices[i][0]) == (stockPrices[i + 1][0] - stockPrices[i][0]) * (start_point[1] - stockPrices[i][1]):\r\n",
    "                res -= 1\r\n",
    "                print(i, _price, res, start_point, \"same\")\r\n",
    "                # continue\r\n",
    "            else:\r\n",
    "                start_point = _price\r\n",
    "                print(i, _price, res, start_point, \"diff\")\r\n",
    "                # continue\r\n",
    "\r\n",
    "        return res\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        ans = 0\n",
    "        last = None\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            # x值不可能相同，因此除以x的差\n",
    "            new = Decimal(y2 - y1) / Decimal(x2 - x1)\n",
    "            if new != last:\n",
    "                ans += 1\n",
    "                last = new\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n == 1: return 0\n",
    "        res = 1\n",
    "        c,d,e,f = stockPrices[0][0],stockPrices[0][1],stockPrices[1][0],stockPrices[1][1]\n",
    "        for i in range(2,n):\n",
    "            a,b,c,d,e,f = c,d,e,f,stockPrices[i][0],stockPrices[i][1]\n",
    "            if (c-a)*(f-b) != (d-b)*(e-a): res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)<3:\n",
    "            return len(stockPrices)-1\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d1_0,p1_0 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d2_1,p2_1 = d2-d1,p2-p1\n",
    "            if d2_1*p1_0!=d1_0*p2_1:\n",
    "                mls += 1\n",
    "                d1_0,p1_0 = d2_1,p2_1\n",
    "            d1,p1 = d2,p2\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d1_0,p1_0 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d2_1,p2_1 = d2-d1,p2-p1\n",
    "            if d2_1*p1_0!=d1_0*p2_1:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d1_0,p1_0 = d2_1,p2_1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        if len(stockPrices) == 1:return 0\n",
    "        if len(stockPrices) == 2:return 1\n",
    "        res = 1\n",
    "        n = len(stockPrices)\n",
    "        A,B = stockPrices[0],stockPrices[1]\n",
    "        for i in range(2,n):\n",
    "            C = stockPrices[i]\n",
    "            if (B[0]-A[0])*(C[1]-B[1]) != (B[1]-A[1])*(C[0]-B[0]):\n",
    "                res += 1\n",
    "            A = B\n",
    "            B = C\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            mls += d21*p10!=d10*p21\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i0,j0 = stockPrices[0]\n",
    "        i1,j1 = stockPrices[1]\n",
    "        i10,j10 = i1-i0,j1-j0\n",
    "        for p in stockPrices[2:]:\n",
    "            i2,j2 = p\n",
    "            i21,j21 = i2-i1,j2-j1\n",
    "            if i21*j10!=i10*j21:\n",
    "                mls += 1\n",
    "            i1,j1 = i2,j2\n",
    "            i10,j10 = i21,j21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d0,p0 = stockPrices[0]\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-d0,p1-p0\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            mls += d21*p10!=d10*p21\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        stockPrices.sort(key=lambda c:c[0])\n",
    "        for i in range(len(stockPrices) - 2):\n",
    "            k1 = (stockPrices[i][1] - stockPrices[i + 1][1]) * (stockPrices[i + 1][0] - stockPrices[i + 2][0])\n",
    "            k2 = (stockPrices[i + 1][1] - stockPrices[i + 2][1]) * (stockPrices[i][0] - stockPrices[i + 1][0])\n",
    "            if k1 != k2:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)<3:\n",
    "            return len(stockPrices)-1\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d1_0,p1_0 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d2_1,p2_1 = d2-d1,p2-p1\n",
    "            if d2_1*p1_0!=d1_0*p2_1:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d1_0,p1_0 = d2_1,p2_1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        px, py = stockPrices[1][0] - stockPrices[0][0], stockPrices[1][1] - stockPrices[0][1]\n",
    "        g = gcd(px, py)\n",
    "        px //= g\n",
    "        py //= g\n",
    "        ans = 1\n",
    "        for i in range(2, len(stockPrices)):\n",
    "            dx, dy = stockPrices[i][0] - stockPrices[i - 1][0], stockPrices[i][1] - stockPrices[i - 1][1]\n",
    "            g = gcd(dx, dy)\n",
    "            dx //= g\n",
    "            dy //= g\n",
    "            if (dx, dy) != (px, py):\n",
    "                px, py = dx, dy\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            if d21*p10!=d10*p21:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
